package leetcode.editor.cn.q1_300.q50;

import java.util.ArrayList;
import java.util.List;

/**
 * @author qidi
 * @date 2021-12-10 11:46:31
 * <p>
 * 思路：
 * 通过列举发现如下规律：
 * n = 4， 共有 4*3*2*1 个数，按照顺序排列后，
 * 第一位（最高位）数为 3*2 一组从小到大循环
 * 第二位为 2 一组循环
 * 第三位为 1 循环
 * 最后以为就是剩余的数字
 */
class Q0060_PermutationSequence {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String getPermutation(int n, int k) {
            List<Integer> nums = new ArrayList<>();
            for (int i = 0; i <= n; i++) {
                nums.add(i);
            }

            // 计算阶乘 由于 k 最大为 9，这里不用考虑溢出
            int range = 1;
            for (int i = 2; i <= n; i++) {
                range *= i;
            }

            StringBuilder sb = new StringBuilder();
            while (range > 0 && k > 0) {
                range /= n--;
                int rem = k % range;
                int i = k / range + (rem == 0 ? 0 : 1);
                sb.append(nums.remove(i));
                if (rem == 0) {
                    // 说明是本轮循环的最后一个数，也就是最大的数
                    for (int j = nums.size() - 1; j > 0; j--) {
                        sb.append(nums.get(j));
                    }
                    return sb.toString();
                } else {
                    k = rem;
                }
            }

            return sb.toString();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0060_PermutationSequence().new Solution();
        System.out.println(solution.getPermutation(3, 2));
        System.out.println(solution.getPermutation(1, 1));
        System.out.println(solution.getPermutation(4, 13));
        System.out.println(solution.getPermutation(3, 3));
        System.out.println(solution.getPermutation(4, 9));
        System.out.println(solution.getPermutation(3, 1));
    }
}